A network is generally defined as a collection of nodes interconnected by means of one or more communication links. End systems connected to the network both send data to, and receive data from, other end systems connected to the network. When an end system is a sender of data, it is referred to as a "source" for that data. When an end system is a receiver of data, it is referred to as a "destination" for that data. Typically, end systems act as both sources and destinations, depending on whether they are sending or receiving data. When acting as a source, an end system typically sends data in the form of messages over a communication link. Messages can flow between communication links and end systems within the network through bridges or routers. Multiple communication links generally are interconnected through a series of bridges and routers in a network.
Each message comprises a sequence of bits. Typically, messages sent over a network are divided into smaller blocks of information called "packets". The flow of packets in the network is usually referred to as "traffic." The packets are sent over the network in accordance with a data transfer protocol which specifies the form of the data as it is being transferred from switch to switch.
Asynchronous transfer mode (ATM) is one of the general classes of digital switching protocols that are used to relay and route traffic through a network. Unlike other known data transfer protocols, such as X.25 or frame relay, ATM transfers data by means of short, fixed length units of information called "cells." In applications utilizing ATM, data packets at a source are first broken up into such fixed length cells, transmitted through the network, and then reassembled at a destination. ATM cells are 53 bytes long consisting of a 5-byte header and a 48-byte information field. The header contains information used by the network to relay the cell from one node to the next over a pre-established route through the network. User data is contained in the remaining 48 bytes of the cell.
The ATM protocol uses a concept of "virtual networking" (also called "virtual channeling") to pass traffic between two end systems in a network. In accordance with this concept, ATM cells always traverse the same path from source to destination, but that path is not reserved for one end system. The path for a particular cell is only set up through the network as that cell is traversing the network. Any time a given end system is not actually occupying a link, another end system is free to use that link.
Accordingly, an ATM connection exists only as sets of routing tables stored in each network node, switch, or other intermediate system along the virtual channel. The routing tables are based on a virtual circuit identifier (VCI) and virtual path identifier (VPI) contained in the cell header. When a virtual channel is established, each node is provided with a set of look-up tables. By accessing the look-up tables, the node first identifies an incoming cell by header address, then routes it through the node to the proper output port.
The cell is thus passed from node to node over the preselected channel. Two cells that are ultimately bound for different destinations may be carried, one after the other, over the same physical medium (e.g., wire) for a common portion of their travel through the network.
With ATM, the successful transmission of packets from source to destination requires successful delivery of all the ATM cells formed from the original information packet. If any one cell is lost, the entire packet must be re-transmitted since the ATM network has no facilities for error correction. If cells are lost along the way, a sender must repeatedly resend the entire original information packet, resulting in an increasing load on the network, thereby creating more network congestion and more cell loss. As a result, ATM networks can operate efficiently only when there is minimal cell loss.
One way to avoid cell loss is to design each communication link and switch to handle the peak load expected through the network. This principle is the basis for Constant Bit Rate service (CBR) in ATM. This results in highly inefficient use of network resources, however, during the non-peak times. To ensure more efficient utilization, the ATM Forum has defined Available Bit Rate service (ABR), which is designed to maximize the utilization (e.g., bandwidth) of network resources while sharing the resources in a "fair" way among network users. The ABR Service is typically used for data traffic.
In order to fairly share network resources between users, a flow control mechanism is used to control the flow of traffic through the network. A common method of flow control (called "rate based" flow control) informs each data source of the maximum data rate at which it can transmit. Rate based flow control in ATM, as defined by the ATM Forum, requires that each data source periodically transmit a resource management (RM) cell. The RM cell loops over the virtual circuit and eventually returns to the data source. As the RM cell flows away from the source, it carries a value called the current cell rate of the data transfer session which informs the switches along the virtual circuit of the allowed cell rate of the session. Each switch along the route can modify another field in the RM cell called the "explicit rate" (ER), reducing it if congestion develops in that switch. When the RM cell returns to the source, the ER value is the maximum rate at which the source may transmit.
Rate based flow control is designed to provide "fairness" in sharing network resources. Specifically, the network bandwidth must be fairly shared among different users of the network. A widely accepted measure of fairness is called "max-min fairness." A bandwidth allocation by definition is max-min fair if, for every session, one session cannot increase its bandwidth without decreasing the bandwidth of sessions of equal or lower bandwidth.
One known method of implementing max-min fairness, known as "Phantom flow control" (Phantom), is a variant of rate based flow control. The Phantom method is an attempt at bounding the rate of each session (i.e., virtual channel) that share a link by the amount of unused bandwidth on that link. Accordingly, each link includes an additional imaginary session, referred to as the "Phantom" session. The Phantom method is described completely in an article (incorporated herein in its entirety, by reference) written by Afek et al., entitled "Phantom, A Simple and Effective Flow Control Scheme," Proc. SIGCOMM '96, Palo Alto, Calif., August 1996.
The Phantom method disclosed in the Afek article is used for rate based flow control of ATM cells passing through an output-buffered ATM switch. The Phantom method measures free bandwidth available on a link over a given time interval and computes a smoothed average by applying an exponential filter to the measured free bandwidth value to produce a value called the "Maximum Allowed Cell Rate" (MACR). The MACR is used to adjust the ER parameter in the RM cells, thereby controlling the maximum source cell rates. A number of variables are required to determine the MACR. In particular, MACR is a function of weighting parameters (alpha values) which are a function of the total number of cells in the output buffer queues ("queue length") relative to a threshold queue value ("queue-threshold"). Alpha values also vary depending on whether the MACR is increasing or decreasing.
FIG. 1 illustrates, in very generalized form, a data packet local area network involving four stations 100, 102, 106, and 108 (hereinafter 100-108), respectively, in which the Phantom flow control method can be utilized. In such a network, each station 100-108 contains software which breaks the packets up into ATM cells and affixes an appropriate header indicating how each cell should be routed through the network. Each station also contains software which receives ATM cells and reassembles the cells into the completed data stream.
Stations 100 and 102 are connected to an ATM switch 110 and stations 106 and 108 are connected to another ATM switch 114. Switches 110 and 114 route cells between the stations 100-108 and control access to the network. For example, station 100 may send cells over media line 116 to media input port 118 of switch 110. Switch 110 may route data cells to a destination station, for example station 106, based on the information in each cell header. To do this, cells are first switched by switch 110 onto output line 112 to switch 114. Switch 114 then routes the cells to station 106. Although only one output line 112 is shown, switch 110 may have several output lines.
Each switch, for example switch 100, acts as a cell relay. Cells that arrive from one of the incoming communication links are examined by the switching process which determines (from the routing codes in the cell header) which output line should be used. The cell is then added to a FIFO buffer queue for that output line which holds cells waiting to be transmitted on the associated outgoing communication link 112.
The Phantom method of computing and stamping the ER value of the RM cell for such a network is shown below.
Every interval of length tau:
choose AINC and ADEC according to Table 1 (below) in view of the following parameters and equations: PA1 ER=min (ER, UTILIZATION.sub.-- FACTOR*MACR.sup.new)
D=unused link capacity of output link of output buffered switch PA2 UTILIZATION.sub.-- FACTOR=the weight of the regular virtual channel vs. the Phantom virtual channel PA2 DECREASE.sub.-- FACTOR=value used for limiting the speed of the decrease in MACR PA2 if(D&gt;MACR.sup.old): MACR.sup.new =MACR.sup.old (1-AINC)+D*AINC PA2 else MACR.sup.new =max (MACR.sup.old (1-ADEC)+D*ADEC, MACR.sup.old* DECREASE.sub.-- FACTOR)
For every Backward RM cell:
TABLE 1 ______________________________________ Computation Of The Smoothing Parameters queue AINC ADEC ______________________________________ queue &lt; Q.sub.-- THRESH alpha alpha/16 Q.sub.-- THRESH &lt; = queue &lt; 2 Q.sub.-- THRESH alpha/2 alpha/8 2 Q.sub.-- THRESH &lt; = queue &lt; 4 Q.sub.-- THRESH alpha/4 alpha/4 4 Q.sub.-- THRESH &lt; = queue &lt; 8 Q.sub.-- THRESH alpha/8 alpha/2 8 Q.sub.-- THRESH &lt; = queue &lt; 16 Q.sub.-- THRESH alpha/16 alpha 16 Q.sub.-- THRESH &lt;= queue alpha/32 2 alpha ______________________________________
One advantage of the Phantom method is that its implementation is relatively inexpensive. However, since the Phantom method was designed for an output-buffered switch, it cannot be applied in a straightforward manner to other architectures such as, is for example, shared memory switches with per-input port memory limits. This alternative architecture generally is less expensive to manufacture than output buffered switches. Accordingly, it would be desirable for the Phantom method to be applicable to these less expensive switch architectures.
Another problem with the Phantom method is that it can cause significant oscillations and instability in the cell rates under certain conditions. Accordingly, it would be desirable to have an apparatus and method that improves the stability of the Phantom flow control method. It is among the general objects of the invention to provide such an apparatus and method.